우리가 만드는 것 🎯
- 데이터 구조: 하나의 우선순위 큐 (PQ).
- 이는 리스트나 큐와 같은 추상 데이터 유형이지만, 특별한 점이 있습니다.
- 모든 항목은 '우선순위'(키)를 갖습니다.
- 당신이 "팝"을 수행할 때, 항상 항상가장 높은 우선순위를 가진 항목을 얻게 됩니다.
- 연산들:
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- 구현 방식: 우리는 이진 최대 힙.
- 왜 힙을 사용하는가? 매우 효율적입니다! 힙은 다음과 같은 성능을 제공합니다:
push: O(log N)pop: O(log N)peek: O(1)
최대 힙이란 무엇인가요?
두 가지 간단한 규칙을 갖춘 이진 트리입니다:
1. 형태 속성
그것은 완전 이진 트리. 모든 레벨이 꽉 차 있지만, 마지막 레벨은 왼쪽부터 차례로 채워집니다. 공백은 없습니다.
잎 노드를 클릭하여 제거하세요
2. 최대 힙 속성
부모 노드의 키는 자식 노드의 키보다 크거나 같음자식 노드의 키보다 크거나 같아야 합니다. 이를 통해 항상 가장 큰 요소가 루트에 위치하게 보장됩니다.가장 큰 요소가 항상 루트에 위치합니다.
트리를 저장하기 💾
트리가 완전이므로, 간단한 배열에 완벽하게 저장할 수 있습니다.
인덱스 계산법 (0기준)
인덱스 i에 있는 노드에 대해:
- 부모
(i - 1) // 2 - 왼쪽 자식
2 * i + 1 - 오른쪽 자식
2 * i + 2
안내:이 공식들을 외우세요! 배열 안의 '트리'를 탐색하는 데 핵심입니다.